/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ZhongJinTao
 * Date: 2024-10-05
 * Time: 21:45
 */
public class Sort {
    // 直接插入排序
    public void insertSort(int[] arr) {
        int n = arr.length;
        if (n == 1) return;

        for (int i = 1; i < n; i++) {
            int tmp = arr[i];
            int j;
            for(j = i - 1; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else break;
            }

            arr[j + 1] = tmp;
        }
    }

    // 希尔排序
    public void shellSort(int[] arr) {
        int grep = arr.length;
        while (grep > 1) {
            grep /= 2;
            shell(arr, grep);
        }
    }

    public void shell(int[] arr, int gap) {
        int n = arr.length;
        for(int i = gap; i < n; i++) {
            int tmp = arr[i];
            int j;
            for(j = i - gap; j >= 0; j -= gap) {
                if(arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = tmp;
        }
    }
}
